/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/palindrome-linked-list
   @Language: C++
   @Datetime: 16-02-09 08:20
   */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
	ListNode *reverse(ListNode *head){
		ListNode *p, *t;
		for(p=head, head=NULL; p; p=t){
			t = p->next;
			p->next = head;
			head = p;
		}
		return head;
	}

public:
	/**
	 * @param head a ListNode
	 * @return a boolean
	 * Tip: find middle of list (p->next)
	 *      reverse mid to end (r)
	 *      judge origin head and reversed list (head and r)
	 *      reverse reversed list (r)
	 *      relink mid to origin list (p->next=r)
	 */
	bool isPalindrome(ListNode* head) {
		// Write your code here
		if (head==NULL || head->next==NULL) return true;
		ListNode H(-1), *p, *q, *r;
		for(H.next=head, p=q=&H; q && (q=q->next); q=q->next,p=p->next);
		q = r = reverse(p->next);	// middle is from p->next to end
		for(; q && q->val==head->val; q=q->next, head=head->next);
		p->next = reverse(r);		// relink to origin list p
		return !q;
	}
};
